package InsertSort;/*
 *
 *@author:    Xavier
 *@data:      2023 - 08 - 26
 *@time:      19:31
 *
 */


import java.util.Arrays;

//直接插入排序
//中心思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，
// 直到所有的记录插入完为止，得到一个新的有序序列
/*
* 时间复杂度：
*   最好情况下：O(N)  ->  数据有序的情况下
*   最坏情况下：O(N^2)  ->  数据逆序的情况下
* 空间复杂度：O(1)
* 稳定性：稳定的排序
*   一个本身就稳定的排序 可以实现为不稳定的排序
*   但一个本身就不稳定的排序 不可能实现为稳定的排序
*
* 当数据越有序的时候 直接插入排序 效率越高
*
* */

public class DirectInsertSort {
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if (arr[j] > tmp) {
                    arr[j+1] = arr[j];
                }else {
                    //arr[j+1] = tmp;
                    break;
                }
            }
            arr[j+1] = tmp;
        }

    }

    public static void main(String[] args) {
        int[] arr = {2,8,7,3,9,5,9,0,0,2};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
